﻿#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>

#define main testmain_binary_search

#define NUM 200

enum SORT_TYPE {Ascend=0, Descend=1};
enum RESULT {SUCCESS=0, FAIL=1};

using namespace std;

void swap_binary_search(int* pa, int* pb)
{
	int temp;
	temp=*pa;
	*pa=*pb;
	*pb=temp;
}

RESULT bubble_sort(int * unsort_array, unsigned int length, SORT_TYPE type=Ascend) 
{
	if(type==Ascend)
	{
	for(unsigned int i=length-1;i>0;i--)///@alex:这边容易犯的错误是，将i>0写成i<0，是思维考虑不全的问题
	{
		for(unsigned int j=0;j<i;j++)
		{
			if(unsort_array[j] > unsort_array[j+1])///@alex:这边容易出的问题是会写成*j>*(j+1)，这个明显也是想歪了的情况
				swap_binary_search(&unsort_array[j] , &unsort_array[j+1]);///@alex:这边也容易出错，因为很容易就写成了:swap_binary_search(int_array[j] , int_array[j+1]); ，这样就会出现很明显的bug了，即传参引用，而不是传参引用，在写函数的时候一定要十分小心这种情况的出现
		}
	}
	return SUCCESS;
	}
	else 
	{
		for(unsigned int i=NUM-1;i>0;i--)///@alex:这边容易犯的错误是，将i>0写成i<0，是思维考虑不全的问题
	{
		for(unsigned int j=0;j<i;j++)
		{
			if(unsort_array[j] < unsort_array[j+1])///@alex:这边容易出的问题是会写成*j>*(j+1)，这个明显也是想歪了的情况
				swap_binary_search(&unsort_array[j] , &unsort_array[j+1]);///@alex:这边也容易出错，因为很容易就写成了:swap_binary_search(int_array[j] , int_array[j+1]); ，这样就会出现很明显的bug了，即传参引用，而不是传参引用，在写函数的时候一定要十分小心这种情况的出现
		}
	}
		return SUCCESS;
	}
}

int * binary_search(int * object_array, unsigned int length, int * begin, int * end,int value)
{
	int * middle=NULL, * no_found=end;

	while (begin!=end)
	{
		middle=begin+(end-begin)/2;
		if(!(*middle>value)&&!(*middle<value))
		{
			return middle;
		}
		if(*middle<value)
		{
			begin=middle;
		}
		else
		{
			end=middle;
		}
	}
	return no_found;
}

unsigned int binary_search(int * object_array, unsigned int length, unsigned int begin, unsigned int end , int value)//todo:注意end的意义！！！//todo:注意，对于未找到变量的处理
{
	unsigned int middle=0, no_found=end;

	while (begin!=end)
	{
		middle=begin+(end-begin)/2;
		if(!(object_array[middle]>value)&&!(object_array[middle]<value))
		{
			return middle;
		}
		if(object_array[middle]<value)
		{
			begin=middle;
		}
		else
		{
			end=middle;
		}
	}
	return no_found;
}

int main(int argc, char* argv[])
{
cout<<"start the demo of bubble sort alogrithm"<<endl<<endl;
	int * int_array=new int[NUM];
	for(int i=0; i<NUM;i++)
		int_array[i]=NUM-i;

	cout<<"the test int array is:"<<endl<<endl;
	for(int i=0; i<NUM;i++)
		cout<<int_array[i]<<'\t';
	cout<<endl;

	//for(int i=0;i<0;i++)
	//	cout<<"test only"<<endl;
	///@alex:注意对于for循环的使用，先对i赋值，然后判断中间的条件是否成立，成立了就执行下一行的语句，再对i做++操作，然后再判断中间的条件。如果条件不满足，就直接退出循环，即可

	if (bubble_sort(int_array,NUM)==SUCCESS)
	{
		cout<<"bubble sort ascend success finished"<<endl<<endl;
	}
	else 
	{
		return 1;
	}

	for(int i=0; i<NUM;i++)
		cout<<int_array[i]<<'\t';
	cout<<endl;

		if (bubble_sort(int_array,NUM, Descend)==SUCCESS)
	{
		cout<<"bubble sort success descend finished"<<endl<<endl;
	}
	else 
	{
		return 1;
	}

for(int i=0; i<NUM;i++)
		cout<<int_array[i]<<'\t';
	cout<<endl;	

	cout<<"test binary search"<<endl;
	int a[11]={10,9,8,7,6,5,4,3,2,1,0};
	copy(&a[0],&a[11],ostream_iterator<int>(cout,"\t"));
	cout<<endl;
	bubble_sort(a,11);
	copy(&a[0],&a[11],ostream_iterator<int>(cout,"\t"));
	cout<<endl;

	int result=0;
	int target;
	cin>>target;
	result=binary_search(a,11,0,11,target);
	cout<<"the target is: "<<a[result]<<endl;
	return 0;
}

